|
In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a property of an intermediate representation (IR), which requires that each variable is assigned exactly once, and every variable is defined before it is used. Existing variables in the original IR are split into ''versions'', new variables typically indicated by the original name with a subscript in textbooks, so that every definition gets its own version. In SSA form, use-def chains are explicit and each contains a single element. SSA was developed by Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck, researchers at IBM in the 1980s. One might expect to find SSA in a compiler for Fortran or C whereas in functional language compilers, such as those for Scheme, ML and Haskell, continuation-passing style (CPS) is generally used. SSA is formally equivalent to a well-behaved subset of CPS excluding non-local control flow, which does not occur when CPS is used as intermediate representation. So optimizations and transformations formulated in terms of one immediately apply to the other. ==Benefits== The primary usefulness of SSA comes from how it simultaneously simplifies and improves the results of a variety of compiler optimizations, by simplifying the properties of variables. For example, consider this piece of code: y := 1 y := 2 x := y Humans can see that the first assignment is not necessary, and that the value of y being used in the third line comes from the second assignment of y . A program would have to perform reaching definition analysis to determine this. But if the program is in SSA form, both of these are immediate:y1 := 1 y2 := 2 x1 := y2 Compiler optimization algorithms which are either enabled or strongly enhanced by the use of SSA include: *constant propagation *(value range propagation ) *sparse conditional constant propagation *dead code elimination *global value numbering *partial redundancy elimination *strength reduction *register allocation 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「static single assignment form」の詳細全文を読む スポンサード リンク
|